125. Valid Palindrome

Question

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

- 1 <= s.length <= 2 * 105
- s consists only of printable ASCII characters.

---

Approach

1. The input string s contains any printable ASCII characters, so it is necessary to remove all symbols and only keep alphanumeric characters.
2. Iterate through the string and only retrieve those that fits based on ASCII code.
3. If the filtered string is empty or there is only one char, it is automatically a palindrome.
4. Else, check each char from the front and back, and stop when we reach the center.
5. Any mismatch during the check means it is NOT a palindrome.

Solution

class Solution {
public:
    bool isPalindrome(string s) {
        //remove spaces and symbols
        string newS;
        
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= 65 && s[i] <= 90){
                //caps letters
                newS += s[i] + 32;
            }else if(s[i] >= 48 && s[i] <= 57){
                //nums
                newS += s[i];
            }else if(s[i] >= 97 && s[i] <= 122){
                //small letters
                newS += s[i];
            }
        }

        if(newS.empty() || newS.size() == 1) return true;
        
        int i = 0, j = newS.size()-1;
        while(i < j){
            if(newS[i] != newS[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};